package main

import (
	"fmt"
	util "go-algorithm-practice/0_util"
	"math"
	"reflect"
	"sort"
)

// 递归实现 [9,8,7,10]
// 每次将数据划分为之前的2块，在各自区域有序，最终合并2块数组 O(N*logN)
func doMergeSortRecursion(arr []int) []int {
	if arr == nil {
		return arr
	}
	arr2 := make([]int, len(arr))
	copy(arr2, arr)
	if len(arr) < 2 {
		return arr2
	}
	MergeSortRecursion(arr2, 0, len(arr2)-1)
	return arr2
}

// 递归实现归并排序
func MergeSortRecursion(arr []int, l, r int) {
	if l == r {
		return
	}
	mid := l + ((r - l) >> 1)
	MergeSortRecursion(arr, l, mid)
	MergeSortRecursion(arr, mid+1, r)
	merge(arr, l, r, mid)
}

func merge(arr []int, l int, r int, mid int) {
	p1 := l
	p2 := mid + 1
	index := 0
	help := make([]int, r-l+1)
	// 取左右半区最小值放入help数组，实现分区内排序
	for p1 <= mid && p2 <= r {
		if arr[p1] <= arr[p2] {
			help[index] = arr[p1]
			p1++
		} else {
			help[index] = arr[p2]
			p2++
		}
		index++
	}
	for p1 <= mid {
		help[index] = arr[p1]
		p1++
		index++

		//help[index++] = arr[p1++]
	}
	for p2 <= r {
		help[index] = arr[p2]
		p2++
		index++
	}

	for i := 0; i < len(help); i++ {
		arr[l+i] = help[i]
	}

}

// 第一步 实现 0-1 2-3 4-5 6-7 上有序
// 第二步 实现 实现 0-3 4-7上有序
// 依次类推
// 使用固定步长的形式 实现
func MergeSort2(arr []int, l, r int) {
	if arr == nil || len(arr) < 2 {
		return
	}
	mergeSize := 1

	N := len(arr)

	for mergeSize < N {
		L := 0
		for L < N {
			if mergeSize >= N-L {
				break
			}
			mid := L + mergeSize
			R := int(math.Min(float64(N-mid-1), float64(mergeSize)))
			merge(arr, L, R, mid)
			L = R + 1
		}

		if mergeSize > N/2 {
			break
		}
		mergeSize <<= 1
	}
}

func main() {
	for i := 0; i < 10000; i++ {
		array := util.RandomArray(100)
		fmt.Println("before: ", array)
		arr2 := doMergeSortRecursion(array)
		fmt.Println("after: ", arr2)
		sort.Ints(array)
		fmt.Println("sort: ", array)
		isEqual := reflect.DeepEqual(array, arr2)
		fmt.Println("两个数组是否一致：", isEqual)
	}
}
